The purpose of this part is to provide background or context for embodiments of the present disclosure set forth in the claims. The description herein is not intended to be an admission of being a prior art.
In a game, in order to find the shortest reachable path between two points, i.e. automatic path-finding, a server will generate a NavMesh (navigation mesh) for a game scene. The NavMesh can be an abstract data structure, consisting of a series of two dimensional convex polygons which represent reachable areas in the game scene. The NavMesh can be created off-line. When a server is loading a game scene, the NavMesh that corresponds to the game scene can be loaded into a memory simultaneously, and then a path-finding algorithm can be applied to find the suitable path. When the game scene becomes larger, the NavMesh grows larger accordingly, and lots of memory will be consumed after the Navmesh is loaded. On the other hand, when the NavMesh grows larger, more nodes would have to be traversed. The huge amount of computation will delay the time of the automatic path-finding. As a result, the consumption of a game server's resources will increase, and game images might get stuck. These make it difficult to provide real-time images/video of high quality for users, and will cause unsatisfying user experience.